#pragma once
#include<iostream>
#include<vector>
using namespace std;

namespace wzy
{
	enum Status
	{
		EXIT,
		DELETE,
		EMPTY
	};
	template<class K,class V>
	struct HashNode
	{
		pair<K, V> _kv;
		Status _s = EMPTY;
	};

	template<class K>
	struct Setkey
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	template<>
	struct Setkey<string>
	{
		size_t operator()(const string& key)
		{
			size_t sum = 0;
			for (int i = 0; i < key.size(); i++)
			{
				sum *= 31;
				sum += key[i];
			}
			return sum;
		}
	};
	template<class K,class V,class Setkey=Setkey<K>>
	class Hash
	{
	public:
		Hash()
		{
			_tables.resize(10);
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}

			if (_n * 10 / _tables.size() >= 7)
			{
				Hash<K, V> newhash;
				newhash._tables.resize(_tables.size() * 2);
				for (int i = 0; i < _tables.size(); i++)
				{
					newhash.Insert(_tables[i]._kv);
				}
				_tables.swap(newhash._tables);
			}


			Setkey h;
			size_t hashi = h(kv.first) % _tables.size();
			while (_tables[hashi]._s == EXIT)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._s = EXIT;
			_n++;
			return true;
		}

		HashNode<K, V>* Find(const K& key)
		{
			Setkey h;
			size_t hashi = h(key) % _tables.size();
			while (_tables[hashi]._s != EMPTY)
			{
				if (_tables[hashi]._s==EXIT&&_tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}
				hashi++;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			Setkey h;
			size_t hashi = h(key) % _tables.size();
			while (_tables[hashi]._s != EMPTY)
			{
				if (_tables[hashi]._s == EXIT && _tables[hashi]._kv.first == key)
				{
					_tables[hashi]._s = DELETE;
					--_n;
					return true;
				}
				hashi++;
			}
			return false;
		}

		void Print()
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIT)
				{
					cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second<<endl;
				}
				else if (_tables[i]._s == DELETE)
				{
					printf("[%d]->D\n", i);
				}
				else if (_tables[i]._s == EMPTY)
				{
					printf("[%d]->\n", i);
				}
			}
		}
	private:
		vector<HashNode<K, V>> _tables;
		int _n = 0;
	};
}
